package com.zgkxzx.算法.排序;

/**
 * 创建者 zgkxzx
 * 日期   12/13/17
 * 描述   排序算法测试
 */

public class Sort {


    /**
     * 冒泡排序
     * 思想：
     *   比较两个值的大小，如果大，进行交换 ，然后一直遍历
     *
     * @param data
     */
    public static void bubbleSort(int[] data) {
        if (data == null || data.length == 0)
            return;
        int temp;
        int size = data.length;
        for (int i = 0; i < size; i++)
            for (int j = i + 0; j < size; j++) {
                if (data[i] > data[j]) {
                    temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
            }

    }


    /**
     * 快速排序
     *
     * @param data
     * @param L
     * @param R
     */
    public static void quickSort2(int[] data, int L, int R) {
        int i = L;
        int j = R;
        int pivot = data[(L + R) / 2];
        while (i <= j) {
            while (data[i] < pivot)
                i++;
            while (data[j] > pivot)
                j--;
            if (i <= j) {
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        }

        if (L < j)
            quickSort2(data, L, j);
        if (i < R)
            quickSort2(data, i, R);
    }

    /**
     * 选择排序
     *   思想：
     *   选择性的扫描一遍将最大值找出 放到最后端，然后再将其他的最大值，再放到后面。。。
     * @param data
     */
    public static void selectSort(int[] data) {
        int length = data.length;
        for (int i = length; i > 0; i--) {
            int maxValueId = getMaxValuePos(data, 0, i - 1);
            int temp = data[i - 1];
            data[i - 1] = data[maxValueId];
            data[maxValueId] = temp;
        }


    }


    private static int getMaxValuePos(int[] data, int start, int end) {
        int max = 0;
        int pos = 0;

        for (int i = start; i < end + 1; i++) {
            if (data[i] > max) {
                max = data[i];
                pos = i;
            }

        }
        return pos;
    }

    /**
     * 插入排序
     *    思想 ：
     *    那后面的一项跟前面的数组列比较，挪动前面的数列，将该项插入到对应的位置，然后再拿下一项跟前面数列比较
     * @param data
     */
    public static void insertSort(int[] data) {
        int length = data.length;

        for (int i = 2; i < length; i++) {
            insert(data, i);
        }
    }

    private static void insert(int[] data, int i) {
        int key = data[i];
        int index = i;

        while (data[index - 1] > key) {
            data[index] = data[index - 1];
            index--;
            if (index == 0)
                break;
        }
        data[index] = key;
    }


}
